package com.leetcode.no330;

// 将 k 视为 nums已有的数 或者 要插入的数
//根据题意，nums 必须有 1
//显然从 [0,1) 开始模拟扩展，一般地，我们取 k 最大，也就是 k = x
//假设 nums 空，我们这样模拟 [0,1) -> [0,2) -> [0,4) -> [0,8) ----> [0,y)，直到 y > n
//因此当 nums(i) ∈ [0,y] 时，可取之为 k 并扩大值域， 否则视为插入一个数 y
//
//作者：francissoft
//链接：https://leetcode-cn.com/problems/patching-array/solution/cjava-jian-dan-qing-xi-de-si-lu-by-franc-1z4j/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
public class Solution {
    public int minPatches(int[] nums, int n) {
        long maxi = 1;
        int i =0, res = 0;
        while(maxi <=n){
            if(i<nums.length && nums[i] <= maxi){
                maxi += nums[i++];
            }else {
                maxi += maxi;
                ++ res;
            }
        }
        return res;
    }
}
